
// 124.二叉树中的最大路径和
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int ans = INT_MIN;
        function<int(TreeNode*)> dfs = [&](TreeNode* pos)
        {
            int ret = pos->val , l = 0 , r = 0;
            if(pos->left) l = max(l , dfs(pos->left));
            if(pos->right) r = max(r , dfs(pos->right));

            ans = max(ret + l + r, ans);
            return max(ret + l , ret + r);
        };
        dfs(root);
        return ans;
    }
};